import java.util.ArrayList;


public class Ex6_6 {

	/*
	Input:
		ATGVWYYYYC
		GYYCFFF

	Output:
		32
		YYC
		YYC

	Input:
		AAAAAASSSSSSSVVVVVVVVTTTTTTTLLLLLL
		SSSSLLLLLTTTTTTTWWWWWWWWWWWPPPPPPPPPP
	Output:
		34
		TTTTLLLLL
		SSSSLLLLL


	Input:
	QTVHQIWMKRLASFFFSMMMRRLLQQSSSTTTFQQDWLLLLLSSSCCSPQPQPQTYTYTYTFFRRRSSMMMLNNNDNDKVWSKLLWPPPPQRMS
	TQDFFSMLRRAAQFFMMRLCCDPPPATATATFPFPMMMDSNSSSDNSQRRQRQRQTFTDTSTCCQVVMNFRMNFRVDFPLLK

	Output:
	59
	LLLLSSSCCSPQPQPQTYTYTYTFFRRRSS
	FFMMRL-CCDPPPATATATFPFPMMMDSNS		


	https://class.coursera.org/bioinformatics-001/forum/thread?thread_id=836

	 */
	
	public String resultV, resultW;
	public Integer max_i, max_j,max_score;
	
	public Ex6_6() {
		resultV = "";
		resultW = "";
		max_i =0;
		max_j= 0;
		max_score = 0;
	}


	public static void main(String[] args) {
		Ex6_6 exer = new Ex6_6();
		ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\input_6_6.txt");
		String v = inputs.get(0);
		String w = inputs.get(1);
		ArrayList<Integer[][]> results = exer.getBacktrack(v, w);
		Integer[][] backt = results.get(0);
		Integer[][] scores = results.get(1);		
		exer.getOutputLCS(scores,backt,v,w,exer.max_i,exer.max_j);
		Utils.writeFile( exer.max_score + "\r\n"   
				+ exer.resultV + "\r\n" 
				+ exer.resultW, 
				"C:\\Users\\josemfer\\Downloads\\out_6_6.txt");
		System.out.println(exer.max_score);
		System.out.println(exer.resultV);
		System.out.println(exer.resultW);

	}

	
	
	private void getOutputLCS(Integer[][] scores, Integer[][] backtrack, 
			String v, String w, Integer i, Integer j) {
		//System.out.println("i=" + i + "   j=" + j);
		if (i == 0 || j == 0 || scores[i][j] == 0) {
			return;
		}
		if (backtrack[i][j] == 0) { // '0' = down
			getOutputLCS(scores,backtrack,v,w,i-1,j);			
			resultV += v.charAt(i-1);
			resultW += "-";

		} else if (backtrack[i][j] == 1) {   // '1' = right 
			getOutputLCS(scores,backtrack,v,w,i,j-1);
			resultV += "-";
			resultW += w.charAt(j-1);

		} else if (backtrack[i][j] == 2) {
			getOutputLCS(scores, backtrack,v,w,i-1,j-1);   //  '2' = diagonal
			resultV += v.charAt(i-1);
			resultW += w.charAt(j-1);			
		}		
	}	

	/*
	 *   '0' = down   '1' = right   '2' = diagonal
	 */
	private ArrayList<Integer[][]> getBacktrack(String v, String w) {	
		ArrayList<Integer[][]> results = null;			
		Integer sigma = 5;
		//String pam250 = "ACDEFGHIKLMNPQRSTVWY";	
		String blosum62 = "ACDEFGHIKLMNPQRSTVWY";		
		 				 
		//Integer[][] pamMatrix = 
			// Utils.readMatrix("C:\\Users\\josemfer\\Downloads\\PAM250.txt");
		Integer[][] pamMatrix = 
		  Utils.readMatrix("C:\\Users\\josemfer\\Downloads\\BLOSUM62.txt");
		
		Integer n = v.length();
		Integer m = w.length();
		Integer s[][] = new Integer[n+1][m+1];
		Integer back[][] = new Integer[n+1][m+1];		
		for (int i=0;i<=n;i++) {
			s[i][0] = 0;
			back[i][0] = 2; 
		}
		for (int j=0;j<=m;j++) {
			s[0][j] = 0;
			back[0][j] = 2; 
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				// calculate down and right
				Integer down = s[i-1][j] - sigma;
				Integer right = s[i][j-1] - sigma;
				// calculate diag				
				char vi = v.charAt(i-1);
				char wj = w.charAt(j-1);
				Integer blosum_i = blosum62.indexOf(vi);
				Integer blosum_j = blosum62.indexOf(wj);
				Integer diag = s[i-1][j-1] + pamMatrix[blosum_i][blosum_j]   ;
				//save score and backtrack matrix			
				Integer score = Utils.max(new Integer[]{down,right,diag,0});			
				s[i][j] = score;
				if (score > this.max_score) {
					this.max_score = score;
					max_i = i;
					max_j = j;
				}				
				//System.out.println("i=" + i + "   j="+j + "   s=" + s[i][j]);
				Integer ind = Utils.maxIndex(new Integer[]{down,right,diag,0});
				if (ind == 3) {
					ind = 2;
				}				
				back[i][j] = ind;	
				
			}				
		}
		results = new ArrayList<Integer[][]>();		
		results.add(back);		
		results.add(s);		
		return results;
	}


}
